package leetcode_401_500;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_429 {
     static class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }
    public static void main(String[] args) {

    }
    private static List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null){
            return ans;
        }
        int d = getD(root, 1);
        for (int i = 0; i < d; i++) {
            ans.add(new ArrayList<>());
        }
        dfs(root, ans, 0);
        return ans;
    }
    private static int getD(Node root, int depth){
        List<Node> children = root.children;
        int d = depth;
        for (Node child : children) {
            d = Math.max(d, getD(child, depth + 1));
        }
        return d;
    }
    private static void dfs(Node node, List<List<Integer>> ans, int depth){
        ans.get(depth).add(node.val);
        for (Node child : node.children) {
            dfs(child, ans, depth + 1);
        }
    }
}
